The present invention relates to a content addressable memory device.
A content addressable memory array (CAM array) has a function to perform coincidence determination of stored data and supplied search data in addition to a read/write function of data, one entry which stores a search data word comprises plural CAM cells, and a word bit of a search candidate is stored in the CAM cells. In each entry, a match line to which the corresponding CAM cells are coupled in parallel is provided. When a search data word and a stored data word of an entry are in agreement, the corresponding match line is maintained in a state of “1”, and when in disagreement, the corresponding match line is driven into a state of “0.”
By identifying a voltage level of the match line, it is possible to determine whether data corresponding to the search data is stored in a table etc., for example. Such a content addressable memory is used for determining of a cache hit or cache miss in a communications router, a cache memory, etc., for example. Routing of an IP packet performed by a network router etc. is carried out by verifying that an IP address which is stored in a content addressable memory provided in the router is in agreement with an IP address which is inputted from the exterior. For example, on the basis of match line information indicative of a coincidence state of the content addressable memory provided in the router, a value which indicates the next destination address is written in the IP packet, and then the IP packet is transmitted from a corresponding port.
In searching operation of CAM, a match line which indicates a state of coincidence/non-coincidence between search data (for example, 80-bit width) and stored data (with an identical width to the search data) of the CAM array is pre-charged to a power supply voltage VDD at a pre-charge period. When the search data and the stored data are in disagreement (henceforth called as “Miss”) by searching, the match line is discharged by a transistor in a CAM cell to a ground voltage GND. When in agreement (henceforth called as “Hit”), on the other hand, discharging of the match line is not performed, but the level of the pre-charge voltage VDD is maintained. It is determined whether the stored data and the search data are in agreement or not, by the aid of the match line having such two states.
The following explains about current consumed at the time of search in a large-scale CAM array, for example, a 20M-bit (256K entries×80 bits) CAM array, which can perform a huge amount of data search concurrently.
Assuming that current consumed by one entry is I_mL when a search result is Miss (that is, charge and discharge current of one match line), current of I_mL×256K is consumed in the above-described large-scale CAM array.
At the time of searching, a search line which indicates a state of search data is charged to the VDD level when search data is “1” (HIGH), and discharged to a GND level when the searching finishes. Assuming that current consumed by a search line per one bit of search data and one entry is I_SL, current of I_SL×256K×80 is consumed in the above-described large-scale CAM array.
At the time of searching operation, a match amplifier circuit which determines a state of a match line of all the entries is also activated concurrently. Assuming that current consumed by a match amplifier circuit for one entry is I_ma, current of I_ma×256K is consumed in the above-described large-scale CAM array.
In this way, in the above-described large-scale CAM array, the current consumed by the match line, the search line, and the match amplifier circuit amounts to (I_ML×256K+I_SL×256K×80+I_ma×256K). This value of the consumption current is very large, and occupies the greater part of the entire consumption current. Moreover, the value of the consumption current increases in proportion to formation of a large-scale capacity and speeding up.
A configuration which reduces the consumption current I_ML in a match line in a CAM array is disclosed by Patent Document 1 (U.S. Pat. No. 6,191,969). That is, in configurations illustrated in FIG. 4 of Patent Document 1 and FIG. 3 of Patent Document 2 (U.S. Pat. No. 6,430,074), a match line of a CAM array is divided into plural blocks. When search result of the first stage block is of Miss, searching in the second stage block is controlled not to be performed, and the match lines of the second and latter stages are pre-charged (or discharged). Accordingly, the pre-charge current is reduced and power lowering is attained.
A configuration which reduces consumption current I_ML in a match line in a CAM array is disclosed also in Patent Document 2. That is, in FIG. 10A of Patent Document 2, by dividing match lines of a CAM array into three or more blocks, and controlling match line pre-charge of the third stage block according to search result (Hit, Miss) of the first stage block, formation of pipeline and speeding up of a clock are attained easily, and the pre-charge current is reduced and power lowering is attained.
A configuration which reduces consumption current I_SL in a search line in a CAM array is disclosed by Patent Document 3 (Japanese Patent Laid-open No. 2003-272386). That is, in Patent Document 3, a match line of a CAM array is divided into three or more, and pre-charge of the second stage is controlled by search result of the first stage. Accordingly, the pre-charge current is reduced. Furthermore, when all the entries are of non-coincidence in the first stage block, search lines of the third stage block and the latter stage blocks are rendered non-active. Accordingly, the consumption current of the search lines is reduced, and power lowering is attained.
A configuration which reduces consumption current I_ML in a match line in a CAM array is disclosed also in Patent Document 4 (Japanese Patent Laid-open No. 2009-158027). That is, in Patent Document 4, searching is performed for every memory cell array, and when search data is in agreement with any of data stored in the memory cell array, a search line driver unit is rendered non-active, and searching is not performed for the subsequent memory cell arrays. Accordingly, it become possible to reduce the number of match lines which need charging when returning to a standby state, and it becomes possible to attain reduction of consumption current.
Considering a case where 80 bits of search data are compared with 80 bits of stored data and non-coincidence (Miss) occurs, the number of bits in non-coincidence may be 1 bit-80 bits. When all of 80 bits are of non-coincidence, driving ability is great and access is quick, because match lines are drawn out to the GND side by search transistors of 80 bits. When only one bit is of non-coincidence, on the other hand, the match line is drawn out to the GND side by a search transistor of one bit, accordingly, the speed is slow. Accordingly, a worst access of searching is the non-coincidence of one bit (henceforth called one-bit miss). That is, an operating frequency in searching a CAM array is decided by the present access in most cases.
A configuration which attains speeding up at the time of a one-bit miss in a CAM array is disclosed by Patent Document 5 (U.S. Pat. No. 6,965,519). That is, in a configuration illustrated in FIG. 1 of Patent Document 5, a match line of a CAM array is divided into plurality, parasitic capacitance of the match line is reduced, and speeding up is attained by adopting a pipeline structure.
In Patent Document 6 (Japanese Patent Laid-open No. 2007-317342), by using a differential amplifier for an amplifier circuit of a match line, a very small amplitude signal of the match line is detected and speeding up of access at the time of a one-bit miss is attained. Moreover, a configuration which reduces consumption current I_ML in a match line in a CAM array is disclosed by Patent Document 6. That is, in a configuration illustrated in Patent Document 6, the pre-charge level of a match line is lowered to a middle voltage level lower than VDD/2, and a sense amplifier which can detect voltage of two states of the middle voltage level and a GND level is used. Accordingly, the pre-charge current of a match line is reduced.
Patent Document 7 (Japanese Patent Laid-open No. Hei 05 (1993)-127872) discloses a semiconductor integrated circuit comprising a sub sense line to which each output of bit comparator circuits of the corresponding group is summarized, and one main sense line for outputting a comparison result, to which each sub sense line is coupled in common via each drive element.
(Patent Document 1) U.S. Pat. No. 6,191,969
(Patent Document 2) U.S. Pat. No. 6,430,074
(Patent Document 3) Japanese Patent Laid-open No. 2003-272386
(Patent Document 4) Japanese Patent Laid-open No. 2009-158027
(Patent Document 5) U.S. Pat. No. 6,965,519
(Patent Document 6) Japanese Patent Laid-open No. 2007-317342
(Patent Document 7) Japanese Patent Laid-open No. Hei 05 (1993)-127872.